package class11;

import class10.TreeTools;
import class10.TreeTools.*;
import java.util.*;

/**
 * <a href="https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/">297. 二叉树的序列化与反序列化</a>
 */
public class Code02_SerializeAndReconstructTree {

    // 前序遍历序列化
    public static String preSerialize(TreeNode root) {
        if (root == null) {
            return null;
        }
        Queue<String> result = new ArrayDeque<>();
        preSerializeRecur(root, result);
        return String.valueOf(result);
    }

    public static void preSerializeRecur(TreeNode root, Queue<String> result) {
        if (root == null) {
            result.add("#");
            return;
        }
        result.add(String.valueOf(root.value));
        preSerializeRecur(root.left, result);
        preSerializeRecur(root.right, result);
    }

    // 前序遍历反序列化
    public static TreeNode preDeserialize(String str) {
        if (str == null || str.isEmpty()) {
            return null;
        }
        str = str.substring(1, str.length() - 1);
        String[] strs = str.split(", ");
        Queue<String> queue = new ArrayDeque<>(Arrays.asList(strs));
        return preDeserializeRecur(queue);
    }

    public static TreeNode preDeserializeRecur(Queue<String> queue) {
        String value = queue.poll();
        if (value == null || "#".equals(value)) {
            return null;
        }
        TreeNode head = new TreeNode(Integer.parseInt(value));
        head.left = preDeserializeRecur(queue);
        head.right = preDeserializeRecur(queue);
        return head;
    }

    // 层序遍历序列化
    public static String levelSerialize(TreeNode root) {
        Queue<String> result = new ArrayDeque<>();
        if (root == null) {
            return String.valueOf(result);
        }
        result.add(String.valueOf(root.value));
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            root = queue.poll();
            if (root.left != null) {
                result.add(String.valueOf(root.left.value));
                queue.add(root.left);
            } else {
                result.add("#");
            }
            if (root.right != null) {
                result.add(String.valueOf(root.right.value));
                queue.add(root.right);
            } else {
                result.add("#");
            }
        }
        return String.valueOf(result);
    }

    // 层序遍历反序列化
    public static TreeNode levelDeserialize(String str) {
        if (str == null || str.isEmpty()) {
            return null;
        }
        // 将字符串转成队列形式
        str = str.substring(1, str.length() - 1);
        String[] strs = str.split(", ");
        Queue<String> datas = new ArrayDeque<>(Arrays.asList(strs));
        if (datas.isEmpty()) {
            return null;
        }
        // 创建根节点，根节点从序列化队列中取元素
        TreeNode root = generateNode(datas.poll());
        // 利用队列开始反序列化
        Queue<TreeNode> queue = new ArrayDeque<>();
        if (root != null) {
            queue.add(root);
        }
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            node.left = generateNode(datas.poll());
            node.right = generateNode(datas.poll());
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        return root;
    }

    public static TreeNode generateNode(String value) {
        if (value == null || value.isEmpty() || "#".equals(value)) {
            return null;
        }
        return new TreeNode(Integer.parseInt(value));
    }

    public static void main(String[] args) {
        TreeNode node = TreeTools.stringToTreeNode("[1,2,3,4,5,6,7,8,9]");
        System.out.println(levelSerialize(node));

        TreeNode treeNode = levelDeserialize(levelSerialize(node));
        System.out.println(levelSerialize(treeNode));
    }

}
